package com.cat.DataStructure04;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/longest-word-in-dictionary/
 * @create 2025/11/26 11:01
 * @since JDK17
 */

public class Solution14 {
    static int N = ((int) 1e4), cnt;
    static int[][] tree = new int[N][26];
    static void insert(String word) {
        int cur = 1;
        for (int i = 0, path; i < word.length(); i++) {
            path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
        }
    }
    static boolean search(String word) {
        int cur = 1;
        for (int i = 0, path; i < word.length() - 1; i++) {
            path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                return false;
            }
            cur = tree[cur][path];
        }
        return true;
    }
    static void clear() {
        for (int i = 1; i <= cnt; i++) {
            Arrays.fill(tree[i], 0);
        }
    }
    public String longestWord(String[] words) {
        Arrays.sort(words, (a, b) -> {  // 根据长度和字典序
            if (a.length() != b.length()) {
                return a.length() - b.length();
            } else {
                return a.compareTo(b);
            }
        });
        cnt = 1;
        String ans = new String("");
        for (var x : words) {
            if (search(x)) {
                insert(x);
                if (ans.length() < x.length()) {
                    ans = x;
                }
            }
        }
        clear();
        return ans;
    }
}
